package oj;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LC40 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> list=new ArrayList<>();
        if(candidates.length==0){
            return list;
        }
        List<Integer> res=new ArrayList<>();
        int n=candidates.length;
        Arrays.sort(candidates);
        dfs(list,res,0,n,target,candidates);
        return list;
    }
    private void dfs(List<List<Integer>> list,List<Integer> res,int begin,int len,int target,int[] candidates){
        if(target==0) {
            list.add(new ArrayList<>(res));
            return;
        }
        if(target<0){
            return;
        }
        for(int i=begin;i<len;i++){
            if(i>begin && candidates[i]==candidates[i-1]){
                continue;
            }
            res.add(candidates[i]);
            dfs(list,res,i+1,len,target-candidates[i],candidates);
            res.remove(res.size()-1);
        }

    }
}
